"""
题目描述：设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。
思路：
主栈存储所有元素，负责正常的 push、pop、top 操作。
辅栈专门记录当前栈中的最小元素，确保 最终设计的方法getMin操作能在常数时间O (1)内完成。

push 操作：
将元素压入主栈。若辅栈为空，或当前元素小于等于辅栈的栈顶元素，则将该元素也压入辅栈（保证辅栈顶始终是当前最小值）。
pop 操作：
从主栈弹出栈顶元素。 若弹出的元素与辅栈的栈顶元素相等，则同时从辅栈弹出栈顶元素（确保辅栈顶始终对应主栈当前的最小值）。
top 操作：
直接返回主栈的栈顶元素（主栈非空时）。
getMin 操作：
直接返回辅栈的栈顶元素（辅栈非空时，因辅栈顶始终是当前最小值）。
通过这种设计，辅栈与主栈保持 "同步过滤" 关系，既不冗余存储非最小值，又能在任何时候通过辅栈顶直接获取当前最小值，实现所有操作的高效性。

辅栈中不止会有一个元素，它会随着主栈的操作动态变化，存储的是主栈在不同阶段的最小元素。
具体来说，辅栈的元素数量与主栈可能相同，也可能不同，取决于入栈元素的值：
当新元素小于等于当前辅栈顶元素时，这个新元素会被同时压入辅栈，此时辅栈长度增加 1
当新元素大于当前辅栈顶元素时，不会压入辅栈，此时辅栈长度不变

例如：
push(5) → 主栈[5]，辅栈[5]（辅栈空，直接入栈）
push(3) → 主栈[5,3]，辅栈[5,3]（3≤5，入辅栈）
push(4) → 主栈[5,3,4]，辅栈[5,3]（4>3，不入辅栈）
push(3) → 主栈[5,3,4,3]，辅栈[5,3,3]（3≤3，入辅栈）
可以看到辅栈会有多个元素，每个元素都对应主栈在某一时刻的最小值。当执行 pop 操作时，只要主栈弹出的元素与辅栈顶元素相等，就同步弹出辅栈顶元素，确保辅栈顶始终是主栈当前的最小值。


"""
class MinStack:
    def __init__(self):
        #初始化数据栈和辅助栈
        self.stack = []       # 主栈，存储所有元素
        self.min_stack = []   # 辅助栈，存储当前时刻主栈当中所有元素的最小值

    def push(self, val: int) -> None:
        """将元素val压入栈"""
        self.stack.append(val)
        # 如果辅助栈为空，或当前元素小于等于辅助栈顶元素，则将其压入辅助栈
        if not self.min_stack or val <= self.min_stack[-1]:
            self.min_stack.append(val)

    def pop(self) -> None:
        #移除栈顶元素 如果主栈顶元素等于辅助栈顶元素，同步弹出辅助栈顶元素
        if self.stack.pop() == self.min_stack[-1]:
            self.min_stack.pop()

    def top(self) -> int:
        """返回栈顶元素"""
        return self.stack[-1]

    def getMin(self) -> int:
        """检索栈中的最小元素"""
        return self.min_stack[-1]

# 测试示例
obj = MinStack()
obj.push(-2)
obj.push(0)
obj.push(-3)
print(obj.getMin()) # -3
obj.pop()
print(obj.top())    # 0
print(obj.getMin()) # -2